public class RedBlackTree {
    public TreeNode root;

    public boolean insert(int val) {
        TreeNode node = new TreeNode(val);
        if(root == null) {
            root = node;
            root.color = Color.BLACK;
            return true;
        }

        TreeNode cur = root;
        TreeNode parent = null;

        while(cur != null) {
            if(cur.val == val) {
                //数值相同的结点不能插入。
                return false;
            } else if(cur.val > val) {
                parent = cur;
                cur = cur.left;
            } else {
                parent = cur;
                cur = cur.right;
            }
        }

        if(parent.val > val) {
            parent.left = node;
        } else {
            parent.right = node;
        }
        node.parent = parent;

        cur = node;

        while(parent != null && parent.color == Color.RED){
            TreeNode grandparent = parent.parent; //一定存在

            if(parent == grandparent.left) {
                TreeNode uncle = grandparent.right;
                if(uncle != null && uncle.color == Color.RED) {
                    uncle.color = Color.BLACK;
                    parent.color = Color.BLACK;
                    grandparent.color = Color.RED;

                    //继续向上调整
                    cur = grandparent;
                    parent = cur.parent;
                } else {
                    // uncle 不存在或者 uncle 是 黑色结点，那就需要进行旋转调整

                    if(cur == parent.right) {
                        //先对 parent 进行左旋，然后交换 cur 与 parent ，之后就会变成下面的代码的情况
                        rotateLeft(parent);
                        TreeNode tmp = parent;
                        parent = cur;
                        cur = parent;
                    }

                    // cur 是 parent 的右孩子，对grandparent 进行右旋
                    rotateRight(grandparent);
                    parent.color = Color.BLACK;
                    grandparent.color = Color.RED;

                    //红黑树已经调整完成，直接退出循环，不用继续调整颜色
                    break;
                }

            } else {
                //parent == grandparent.right
                TreeNode uncle = grandparent.left;
                if(uncle != null && uncle.color == Color.RED) {
                    uncle.color = Color.BLACK;
                    parent.color = Color.BLACK;
                    grandparent.color = Color.RED;

                    //继续向上调整
                    cur = grandparent;
                    parent = cur.parent;
                } else {
                    // uncle 不存在或者 uncle 是 黑色结点，那就需要进行旋转调整

                    if(cur == parent.left) {
                        //先对 parent 进行右旋，然后交换 cur 与 parent变成下面的情况
                        rotateRight(parent);

                        TreeNode tmp = parent;
                        parent = cur;
                        cur = tmp;
                    }

                    //此时 cur 是 parent 的 右孩子
                    rotateLeft(grandparent);
                    grandparent.color = Color.RED;
                    parent.color = Color.BLACK;

                    //红黑树已经调整完成，直接退出循环，不用继续调整颜色
                    break;
                }

            }
        }
        root.color = Color.BLACK;

        return true;
    }

    //右旋
    private void rotateRight(TreeNode parent) {
        TreeNode cur = parent.left;
        TreeNode curR = cur.right;
        TreeNode Pparent = parent.parent;

        parent.left = curR;
        if(curR != null) {
            curR.parent = parent;
        }

        cur.right = parent;
        parent.parent = cur;
        cur.parent = Pparent;

        if(root == parent) {
            root = cur;
        } else if(Pparent.left == parent) {
            Pparent.left = cur;
        } else {
            Pparent.right = cur;
        }
    }


    //左旋
    private void rotateLeft(TreeNode parent) {
        TreeNode cur = parent.right;
        TreeNode curL = cur.left;
        TreeNode Pparent = parent.parent;

        parent.right = curL;
        if(curL != null) {
            curL.parent = parent;
        }

        cur.left = parent;
        parent.parent = cur;
        cur.parent = Pparent;

        if(root == parent) {
            root = cur;
        } else if(Pparent.left == parent) {
            Pparent.left = cur;
        } else {
            Pparent.right = cur;
        }
    }

}
